package class_0904BinarySearchTree;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Queue;
public class BinaryTree{
    public static class TreeNode<T>{
        T val;
        TreeNode<T> left;
        TreeNode<T> right;
        public TreeNode(T val) {
            this.val = val;
        }
    }
    private TreeNode<Integer> root; //这里指定整数类型。

    /**
     * 创建一棵二叉树 返回这棵树的根节点
     * @return 返回一个二叉树的头节点
     */
    public TreeNode<Integer> createTree() {
        TreeNode<Integer> root = new TreeNode<Integer>(8);
        TreeNode<Integer> node1 = new TreeNode<>(3);
        TreeNode<Integer> node2 = new TreeNode<>(10);
        root.left = node1;
        root.right = node2;

        //左子树
        TreeNode<Integer> node3 = new TreeNode<>(1);
        TreeNode<Integer> node4 = new TreeNode<>(6);
        node1.left = node3;
        node1.right = node4;

        TreeNode<Integer> node5 = new TreeNode<>(4);
        TreeNode<Integer> node6 = new TreeNode<>(7);
        node4.left = node5;
        node4.right = node6;

        //右子树
        TreeNode<Integer> node7 = new TreeNode<>(14);
        node2.right = node7;

        node7.right = new TreeNode<>(13);
        return root;

    }

    //在写个构造方法
    public BinaryTree() {
        root = createTree();
    }

    // 前序遍历
    public void preOrder(TreeNode<Integer> root) {
        if(root!=null){
            System.out.println(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // 中序遍历
    void inOrder(TreeNode<Integer> root) {
        if(root!=null){
            inOrder(root.left);
            System.out.println(root.val);
            inOrder(root.right);
        }
    }

    // 后序遍历
    void postOrder(TreeNode<Integer> root) {
        if(root!=null){
            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.val);
        }
    }
    /**
     * 先序遍历:根>>左>>右
     * ///前序遍历非递归
     */
    public void preOrderUnRec(TreeNode<Integer> root){
        //用栈模拟递归。
        if(root!=null){
            //初始状态
            Stack<TreeNode<Integer>> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                //从栈中弹出一个元素---由于根节点，先打印处理。
                TreeNode<Integer> node = stack.pop();
                System.out.println(node.val);
                //先压右，再压左-因为栈后进先出，下次循环会处理左子树。
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
                //循环往复
            }
        }
    }

    /**
     * 中序非递归遍历
     * 左<根<右
     * @param root 头节点
     */
    public void inOrderUnRec(TreeNode<Integer> root) {
        //用栈模拟递归。
        if (root != null) {
            //初始状态
            Stack<TreeNode<Integer>> stack = new Stack<>();
            TreeNode<Integer> cur = root;
            while (cur!=null || !stack.isEmpty()) {
                //先从左走到死
                if(cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }
                else{   // cur==null
                    //回到子树的根节点
                    cur = stack.pop();
                    System.out.println(cur.val);
                    // 转向右子树
                   cur = cur.right;
                }
                //如此处理，相当于只有左和根，  右被分解成了左和根
            }
        }
    }
    /**
     *      后序遍历非递归-双栈实现
     *      stack1-处理栈
     *      stack2-收集栈
     */
    public void postOrderUnRec(TreeNode<Integer> root){
        if(root!=null){
            //初始状态
            Stack<TreeNode<Integer>> stack1 = new Stack<>();
            Stack<TreeNode<Integer>>  stack2 = new Stack<>();
            stack1.push(root);
            while(!stack1.isEmpty()){
                //stack2收集stack1弹出的节点
                TreeNode<Integer> node = stack1.pop();
                stack2.push(node);
                //先压左，再压右。--（如果有）
                if(node.left!=null) {
                    stack1.push(node.left);
                }
                if(node.right!=null){
                    stack1.push(node.right);
                }
                //stack1不为空就重复该过程。
            }
            //输出stack2打印即可。
            while(!stack2.isEmpty()){

                System.out.println(stack2.pop().val);
            }
        }
    }
    /**
     * 单栈实现
     * 更加省空间!!!
     * 先尽可能往左走,再全力往右走.这就是后序遍历递归序.
     * 为什么要设置lastVisited这个变量呢?为什么处理根节点之后,弹栈要标记这个节点呢?
     * @param head 头节点
     */
    public static void postOrderUnRecSingleStack(TreeNode<Integer> head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        TreeNode<Integer> cur = head;
        TreeNode<Integer> lastVisited = null;
        //想象递归的走向,然后循环分支写/
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                //无脑往左走.
                stack.push(cur);
                cur = cur.left;
            } else {
                //左边走空了,开始回退上一个根节点往右边走.
                TreeNode<Integer> peekNode = stack.peek();
                // 若右子节点存在且没有访问过，则先遍历右子节点
                if (peekNode.right != null && lastVisited != peekNode.right) {
                    cur = peekNode.right;
                } else {
                    // 右子节点不存在或已访问，处理(打印)当前子树根节点.
                    System.out.println(peekNode.val + " ");
                    lastVisited = stack.pop();
                }
            }
        }
    }

    // 在每次开始计算之前，将 nodeSize 重置为 0，确保每次调用都不会累加之前的结果。
    public static int nodeSize; /// 静态变量
    /**
     * 获取树中节点的个数：遍历思路
     */
    void calculateSize(TreeNode<Integer> root) {
        //用栈模拟递归。
        if(root!=null){
            //初始状态
            Stack<TreeNode<Integer>> stack = new Stack<>();
            stack.push(root);
            //总之遍历完节点计数就完事了。
            while(!stack.isEmpty()){
                TreeNode<Integer> node = stack.pop();
                nodeSize++;
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
            }
        }
    }

    /**
     * 获取节点的个数：子问题的思路
     *
     * @param root
     * @return
     */
    int calculateSize2(TreeNode<Integer> root) {
        return root == null ? 0 : calculateSize2(root.left) + calculateSize2(root.right) + 1;
    }

    int calculateSize2UnRec(TreeNode<Integer> root) {
        if (root == null) {
            return 0;
        }

        int nodeSize = 0;
        Stack<TreeNode<Integer>> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode<Integer> node = stack.pop();
            nodeSize++;  // 每次访问一个节点时，增加计数

            // 先压右子节点，再压左子节点，这样出栈时先处理左子节点
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return nodeSize;
    }


    //静态变量--每次计数使用要重置
    public static int leafSize = 0;
    /**
     * 获取叶子节点的个数：遍历思路
     */
    void getLeafNodeCount1(TreeNode<Integer> root) {
        if(root==null){
            return ;
        }
        //叶子节点判定
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /**
     获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode<Integer> root) {
        //空节点
        if(root==null){
            return 0;
        }
        //叶子节点
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    /**
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode<Integer> root, int k) {
        // 如果树为空，返回0，表示没有节点
        if (root == null) {
            return 0;
        }
        // 如果k==0，表示当前节点就是第K层的节点，返回1
        if (k == 0) {
            return 1;
        } else {
            // 递归地计算左右子树第K-1层的节点数之和
            return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
        }
    }


    /**
       获取二叉树的高度
       时间复杂度：O(N)
     */
    int getHeight(TreeNode<Integer> root) {
        if(root==null){
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }


    /**
     * 检测值为 val 的元素是否存在
     * 使用深度优先搜索遍历一遍即可。
     *
     * @param root 根节点
     * @param val 要查找的值
     * @return 找到的节点，如果不存在则返回 null
     */
    TreeNode<Integer> find(TreeNode<Integer> root, Integer val) {
        if(root!=null){
            Stack<TreeNode<Integer>>  stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode<Integer> node = stack.pop();
                if(node.val.equals(val)) {
                    return node;
                }
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
            }
        }
        return null;
    }

    /**
     * 层序遍历： 广度优先遍历
     * @param root
     */
    void levelOrder(TreeNode<Integer> root) {
        if(root!=null){
            Queue<TreeNode<Integer>> queue = new ArrayDeque<>(); //使用双端队列。
            queue.offer(root);//根节点入队
            while(!queue.isEmpty()){
                TreeNode<Integer> node = queue.poll();
                System.out.println(node.val);
                if(node.left!=null) {
                    queue.offer(node.left);
                }
                if(node.right !=null){
                    queue.offer(node.right);
                }
            }
        }
    }


    /**
     * 检查二叉树是否为完全二叉树
     * 简单思路:广度优先遍历（BFS）
     * 先观察:完全二叉树不存在左孩子不存在但右孩子存在的情况.
     * 再次观察发现:宽度遍历若第一次遇见非二度节点,那么后序节点为叶子节点.
     * 反证法可以证明
     */
    boolean isCompleteTree(TreeNode<Integer> root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode<Integer>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;

        while (!queue.isEmpty()) {
            TreeNode<Integer> node = queue.poll();
            TreeNode<Integer> left = node.left;
            TreeNode<Integer> right = node.right;

            if (leaf) {
                // 如果已经遇到叶子节点，之后的节点必须都是叶子节点
                if (left != null || right != null) {
                    return false;
                }
            } else {
                if (left == null && right != null) {
                    // 如果左子节点为空但右子节点不为空，则不是完全二叉树
                    return false;
                }
                if (left != null && right == null) {
                    // 如果左子节点存在而右子节点为空，则标记为叶子节点
                    leaf = true;
                }

                // 入队左右子节点
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
        }
        return true;
    }
}